package main

func searchRange(nums []int, target int) []int {
	result := []int{-1, -1}
	numsLen := len(nums)
	lp, rp := 0, numsLen-1
	for lp <= rp {
		mid := int((lp + rp) / 2)
		midVal := nums[mid]
		if midVal == target {
			llp, lrp := lp, mid
			for llp <= lrp {
				lmid := int((llp + lrp) / 2)
				lmidVal := nums[lmid]
				if lmidVal < target {
					llp = lmid + 1
				} else if lmidVal == target {
					lrp = lmid - 1
				}
			}
			rlp, rrp := mid, rp
			for rlp <= rrp {
				rmid := int((rlp + rrp) / 2)
				rmidVal := nums[rmid]
				if rmidVal > target {
					rrp = rmid - 1
				} else if rmidVal == target {
					rlp = rmid + 1
				}
			}
			result = []int{llp, rrp}
			break
		} else if midVal > target {
			rp = mid - 1
		} else if midVal < target {
			lp = mid + 1
		}
	}
	return result
}
